package 力扣91;

/**
 * @ClassName : _1381_设计一个支持增量操作的栈_lc题解_模拟优化
 * @Author : 骆发茂
 * @Date: 2021/12/14 22:38
 * @Description : * @Description : https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/
 * https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/solution/she-ji-yi-ge-zhi-chi-zeng-liang-cao-zuo-de-zhan-by/
 *
 * 这里是把添加的方法，添加到add[]，新的辅助数组中
 * push获取就正常放入stack中，
 * pop提取方法就是让stack[top] + add[top];
 *
 */
public class Day3_1381_设计一个支持增量操作的栈_lc题解_模拟优化 {

    class CustomStack {
        int[] stack;
        int[] add;
        int top;

        public CustomStack(int maxSize) {
            stack = new int[maxSize];
            add = new int[maxSize];
            top = -1;
        }

        public void push(int x) {
            if (top != stack.length - 1) {
                ++top;
                stack[top] = x;
            }
        }

        public int pop() {
            if (top == -1) {
                return -1;
            }
            int ret = stack[top] + add[top];
            if (top != 0) {
                add[top - 1] += add[top];
            }
            add[top] = 0;
            --top;
            return ret;
        }

        //方法二：模拟优化，是把累加至 add[top - 1] 处，
        public void increment(int k, int val) {
            //k-1必定正数，top可能是-1，说明里面一个数都没有了，就没办法添加数了
            int limit = Math.min(k - 1, top);
            if (limit >= 0) {
                add[limit] += val;
            }
        }
    }
}